//
// Description: 313. 超级丑数
// Created by Loading on 2021/8/9.
//

#include <bits/stdc++.h>

using namespace std;

/* 动态规划，O(nm) */
int nthSuperUglyNumber_DP(int n, vector<int> &primes) {
    // 标记每个质数的倍数，初始值都为 1
    vector<int> multiple(primes.size(), 1);

    // 动态规划数组，dp[i] 表示第 i 个丑数
    vector<int> dp;
    dp.emplace_back(0);
    dp.emplace_back(1);
    for (int i = 2; i <= n; ++i) {
        // 找到倍数 * 质数的最小值
        int num = INT_MAX;
        for (int j = 0; j < primes.size(); ++j) {
            num = min(num, dp[multiple[j]] * primes[j]);
        }
        dp.emplace_back(num);

        // 更新倍数，注意：由于 dp 数组无重复，所以需要更新所有相乘等于 dp[i] 的质数的倍数
        for (int j = 0; j < primes.size(); ++j) {
            if (dp.back() == dp[multiple[j]] * primes[j]) {
                multiple[j]++;
            }
        }
    }

    return dp.back();
}

/* 优先级队列，小顶堆，O(nmlogn) */
int nthSuperUglyNumber(int n, vector<int> &primes) {
    unordered_set<long long> s;
    priority_queue<long long, vector<long long>, greater<>> p;
    s.insert(1);
    p.emplace(1);
    int ugly = 1;
    for (int i = 0; i < n; ++i) {
        ugly = p.top();
        p.pop();
        for (auto &prime : primes) {
            long long temp = ugly * prime;
            if (!s.count(temp)) {
                s.insert(temp);
                p.emplace(temp);
            }
        }
    }

    return ugly;
}

int main() {
    vector<int> primes = {2, 7, 13, 19};
    int n = 12;
    cout << nthSuperUglyNumber(n, primes) << endl;
    cout << nthSuperUglyNumber_DP(n, primes) << endl;
}